package com.fr.lintcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
 * @author 付荣
 * @version 创建时间：2018年12月20日 下午6:02:51
 */
public class Q1002 {

	/**
	 * @param routes
	 *            : a list of bus routes
	 * @param S
	 *            : start
	 * @param T
	 *            : destination
	 * @return: the least number of buses we must take to reach destination
	 */
	public int numBusesToDestination(int[][] routes, int S, int T) {
		// 站点和线路的关系
		Map<Integer, Set<Integer>> routeMap = new HashMap<>();
		for (int i = 0; i < routes.length; i++) {
			for (int j = 0; j < routes[i].length; j++) {
				Set<Integer> line = routeMap.get(routes[i][j]);
				if (line == null) {
					line = new HashSet<>();
					routeMap.put(routes[i][j], line);
				}
				line.add(i);
			}
		}
		Set<Integer> sites = new HashSet<>();
		Set<Integer> lines = new HashSet<>();
		Set<Integer> tmp = routeMap.get(S);
		int count = 1;
		while (tmp != null && tmp.size() > 0) {
			Set<Integer> tmp1 = new HashSet<>();
			for (int line : tmp) {
				if (!lines.contains(line)) {
					lines.add(line);
					for (int site : routes[line]) {
						if (site == T) {
							return count;
						}
						if (!sites.contains(site)) {
							sites.add(site);
							tmp1.addAll(routeMap.get(site));
						}
					}
				}
			}
			tmp1.removeAll(lines);
			tmp.clear();
			tmp.addAll(tmp1);
			count++;
		}
		return -1;
	}

	@Test
	public void testA() {
		int[][] routes = { { 1, 2, 7 }, { 3, 6, 7 } ,{2,3,8}};
		int S = 2;
		int T = 111;
		System.out.println(numBusesToDestination(routes, S, T));
	}
}
